{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindrome Removal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumMoves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除回文子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>arr</code>，每一次操作你都可以选择并删除它的一个 <strong>回文</strong> 子数组&nbsp;<code>arr[i], arr[i+1], ..., arr[j]</code>（ <code>i &lt;= j</code>）。</p>\n",
    "\n",
    "<p>注意，每当你删除掉一个子数组，右侧元素都会自行向前移动填补空位。</p>\n",
    "\n",
    "<p>请你计算并返回从数组中删除所有数字所需的最少操作次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,2]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,3,4,1,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>先删除 [4]，然后删除 [1,3,1]，最后再删除 [5]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 20</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindrome-removal](https://leetcode.cn/problems/palindrome-removal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindrome-removal](https://leetcode.cn/problems/palindrome-removal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2]', '[1,3,4,1,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        f=[[n]*n for i in range(n)]\n",
    "        g=[None]*n\n",
    "\n",
    "        for i,x in enumerate(arr):\n",
    "            f[i][i]=1\n",
    "            g[i]=[j for j in range(i,n) if x==arr[j]]\n",
    "        \n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                if i==j-1:\n",
    "                    f[i][j]=int(arr[i]!=arr[j])+1\n",
    "                else:\n",
    "                    if arr[i]==arr[j]:\n",
    "                        f[i][j]=f[i+1][j-1]\n",
    "                    for k in g[i]:\n",
    "                        if k>=j:\n",
    "                            break\n",
    "                        f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])\n",
    "        return f[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "\n",
    "        for l in range(1, n + 1):\n",
    "            for i in range(1, n + 1):\n",
    "                j = i + l - 1\n",
    "                if j > n:\n",
    "                    break\n",
    "                if i == j:\n",
    "                    dp[i][j] = 1\n",
    "                    continue\n",
    "                dp[i][j] = float('inf')\n",
    "                for k in range(i, j):\n",
    "                    if arr[k - 1] == arr[j - 1]:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k - 1] + max(1, dp[k + 1][j - 1]))\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k][j - 1] + 1)\n",
    "        return dp[1][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[n] * n for i in range(n)]\n",
    "        g = [None] * n \n",
    "        for i, x in enumerate(arr):\n",
    "            f[i][i] = 1\n",
    "            # 预处理找到 [i, n) 范围内所有与 a[i] 相等的值的下标，减少无效遍历\n",
    "            g[i] = [j for j in range(i, n) if x == arr[j]]\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if i == j - 1:\n",
    "                    f[i][j] = int(arr[i] != arr[j]) + 1\n",
    "                else:\n",
    "                    if arr[i] == arr[j]:\n",
    "                        f[i][j] = f[i + 1][j - 1]\n",
    "                    for k in g[i]:\n",
    "                        if k >= j:\n",
    "                            break\n",
    "                        f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j])\n",
    "\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "\n",
    "        for l in range(1, n + 1):\n",
    "            for i in range(1, n + 1):\n",
    "                j = i + l - 1\n",
    "                if j > n:\n",
    "                    break\n",
    "                if i == j:\n",
    "                    dp[i][j] = 1\n",
    "                    continue\n",
    "                dp[i][j] = float('inf')\n",
    "                for k in range(i, j + 1):\n",
    "                    if arr[k - 1] == arr[j - 1]:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k - 1] + max(1, dp[k + 1][j - 1]))\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k][j - 1] + 1)\n",
    "        return dp[1][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, arr: List[int]) -> int:\n",
    "        lens = len(arr)\n",
    "        if lens == 1:\n",
    "            return 1\n",
    "        dp = [[float(\"inf\") for _ in range(lens)] for _ in range(lens)]\n",
    "\n",
    "        for i in range(lens):\n",
    "            for j in range(lens):\n",
    "                if i > j:\n",
    "                    dp[i][j] = 0\n",
    "                elif i == j:\n",
    "                    dp[i][j] = 1\n",
    "\n",
    "        for sublens in range(lens):\n",
    "            for i in range(lens-sublens):\n",
    "                j = i + sublens\n",
    "                for k in range(i, j+1):\n",
    "                    if arr[k] == arr[j]:\n",
    "                        if k == 0:\n",
    "                            dp[i][j] = min(dp[i][j], max(1, dp[k+1][j-1]))\n",
    "                        elif k == lens-1:\n",
    "                            dp[i][j] = min(dp[i][j], dp[i][k-1]+1)\n",
    "                        else:\n",
    "                            dp[i][j] = min(dp[i][j], dp[i][k-1]+max(1, dp[k+1][j-1]))\n",
    "\n",
    "        return dp[0][lens-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        @cache \n",
    "        def f(i, j):\n",
    "            if i>j:\n",
    "                return 0 \n",
    "            if i==j:\n",
    "                return 1 \n",
    "            ans = 1 + f(i+1, j)\n",
    "            for k in range(i+1, j+1):\n",
    "                if a[i]==a[k]:\n",
    "                    if k-i>1:\n",
    "                        tmp = f(i+1, k-1)\n",
    "                    else:\n",
    "                        tmp = 1\n",
    "                    ans = min(ans, tmp + f(k+1, j))\n",
    "            return ans \n",
    "        return f(0, n-1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, arr: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return 1\n",
    "            if i == j:\n",
    "                return 1\n",
    "            ans = inf\n",
    "            if arr[i] == arr[j]:\n",
    "                ans = dfs(i + 1, j - 1)\n",
    "            return min(ans, min(dfs(i, k) + dfs(k + 1, j) for k in range(i, j)))\n",
    "        return dfs(0, len(arr) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, arr: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==j:\n",
    "                return 1\n",
    "            if i>j:\n",
    "                return 0\n",
    "            if i+1==j:\n",
    "                return 2 if arr[i]!=arr[j] else 1\n",
    "            res=1+dfs(i+1,j)\n",
    "            for k in range(i+1,j+1):\n",
    "                if arr[i]==arr[k]:\n",
    "                    res=min(res,max(dfs(i+1,k-1),1)+dfs(k+1,j))\n",
    "            return res\n",
    "        return dfs(0,len(arr)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param arr:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def get_min(l, r):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if l == r:\n",
    "                return 1\n",
    "            if l + 1 == r:\n",
    "                if arr[l] == arr[r]:\n",
    "                    return 1\n",
    "                return 2\n",
    "\n",
    "            curval = arr[l]\n",
    "            plist = []\n",
    "            for i in range(l + 1, r + 1):\n",
    "                if arr[i] == curval:\n",
    "                    plist.append(i)\n",
    "            ans = math.inf\n",
    "            for i in plist:\n",
    "                if i != r:\n",
    "                    ans = min(ans, get_min(l, i) + get_min(i + 1, r))\n",
    "            if arr[l] == arr[r]:\n",
    "                x1 = get_min(l+1, r-1)\n",
    "                ans = min(ans, x1)\n",
    "            ans = min(ans, 1 + get_min(l + 1, r))\n",
    "            return ans\n",
    "        return get_min(0, len(arr) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param arr:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_min(l, r):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if l == r:\n",
    "                return 1\n",
    "            if l + 1 == r:\n",
    "                if arr[l] == arr[r]:\n",
    "                    return 1\n",
    "                return 2\n",
    "\n",
    "\n",
    "            curval = arr[l]\n",
    "            plist = []\n",
    "            for i in range(l + 1, r + 1):\n",
    "                if arr[i] == curval:\n",
    "                    plist.append(i)\n",
    "            xx2 = math.inf\n",
    " \n",
    "            xx2 = 1 + get_min(l + 1, r)\n",
    "            ans = math.inf\n",
    "            for i in plist:\n",
    "                if i != r:\n",
    "                    ans = min(ans, get_min(l, i) + get_min(i + 1, r))\n",
    "            if arr[l] == arr[r]:\n",
    "                x1 = get_min(l+1, r-1)\n",
    "                ans = min(ans, x1)\n",
    "            ans = min(ans, xx2)\n",
    "            return ans\n",
    "\n",
    "        return get_min(0, len(arr) - 1)\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.minimumMoves([1,4,1,1,2,3,2,1]))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
